//快速排序
function quickSort (arr,startIndex,endIndex){
    //递归结束条件 startIndex大于或等于endIndex
    if(startIndex >= endIndex){
        return;
    }
    //得到基准元素位置
    //let pivotIndex = partition1(arr,startIndex,endIndex);
    let pivotIndex = partition2(arr,startIndex,endIndex);
    //根据基准元素 分成两部分进行递归排序
    quickSort(arr,startIndex,pivotIndex-1);
    quickSort(arr,pivotIndex +1,endIndex)
}

/**
 * 分治 双边循环法
 * @param arr 待交换的数组
 * @param startIndex 起始下标
 * @param endIndex 结束下标
 */

 function partition (arr, startIndex,endIndex){
     //取第一个位置 也可以随机 的元素作为基准元素
     let pivot = arr[startIndex];
     let left = startIndex;
     let right = endIndex;
     while(left != right){
         //控制right 比较并左移
         while(left <right && arr[right] > pivot){
             right --;
         }
         //控制 left 比较 并右移
         while(left <right && arr[left]<= pivot){
             left ++;
         }
         //交换left 和right所指向的元素
         if(left < right){
             let p = arr[left]
             arr[left] = arr[right]
             arr[right] = p
         }
     }
     //pivot 和 指针重合点交换
     arr[startIndex] = arr[left]
     arr[left] = pivot;
     return left
 }
 /**
  * 分治 单边循环法
  * @param arr 待交换的数组
  * @param startIndex 起始下标
  * @param endIndex 结束下标
  */

  function partition2(arr,startIndex,endIndex){
      // 取第一个位置 也可以随机 的元素作为基准元素
      let pivot =arr[startIndex]
      let mark = startIndex
      for(let i =startIndex+1;i<=endIndex;i++){
          if(arr[i]<pivot){
              mark++;
              let p = arr[mark];
              arr[mark] = arr[i];
              arr[i] = p;
          }
      }
      arr[startIndex] = arr[mark];
      arr[mark] = pivot
      return mark
  }
 let arr = [4,4,6,5,3,2,8,1];
 function main(){
     
     quickSort(arr,0,arr.length-1);

 }
 main()
 console.log(arr)
